package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/11 17:40
 * https://leetcode.cn/problems/network-delay-time/
 */
public class Title743II {

    class State{
        int id;

        //startId -> curId的距离
        int distance;

        public State(int id, int distance) {
            this.id = id;
            this.distance = distance;
        }
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        //构建图  <i, <j, value>>
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] paths : times) {
            graph.computeIfAbsent(paths[0], g -> new HashMap<>()).put(paths[1], paths[2]);
        }
        //(1, n) k号节点到其他节点的距离
        int[] des = new int[n + 1];
        Arrays.fill(des, Integer.MAX_VALUE);
        //到自身的距离为0
        des[k] = 0;
        Queue<State> queue = new PriorityQueue<>((a, b) -> Integer.compare(a.distance, b.distance));
        queue.offer(new State(k, 0));
        while (!queue.isEmpty()) {
            State state = queue.poll();
            int curId = state.id;
            //当前start到该节点的距离
            int curDistance = state.distance;
            if (curDistance > des[curId]) {
                continue;
            }
            //将当前id的相邻节点加入队列
            Map<Integer, Integer> integerIntegerMap = graph.getOrDefault(curId, new HashMap<>());
            Set<Integer> integers = integerIntegerMap.keySet();
            for (Integer nextId : integers) {
                //当前curId -> nextId 的距离+ des[curId]
                int nextDistance = integerIntegerMap.get(nextId) + des[curId];
                if (nextDistance < des[nextId]) {
                    des[nextId] = nextDistance;
                    queue.offer(new State(nextId, nextDistance));
                }
            }
        }
        int max = 0;
        for (int i = 1; i < des.length; i++) {
            if (des[i] == Integer.MAX_VALUE) {
                return -1;
            }
            max = Math.max(max, des[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        
    }
}
